// 给定一个整数 n，生成所有由 1 ... n 为节点所组成的 二叉搜索树 。

// 外部暴露接口
function generateTrees(n: number) {
  if (n === 0) {// 安全检测
    return [];
  }
  return _buildTrees(1, n);
}
// 生成树的方法
function _buildTrees(low: number, high: number) {
  const res: TreeNode[] = [];// 结果数组
  if (low > high) {
    return [null]; // 递归出口：注意这里需要返回null节点
  }
  if (low === high) {
    return [new TreeNode(low)];//  递归出口：返回根节点
  }
  for (let i = low; i <= high; i++) {
    const leftTrees = _buildTrees(low, i - 1);
    const rightTrees = _buildTrees(i + 1, high);
    for (let leftNode of leftTrees) {// 遍历左右子树数组组合得到二叉搜索树结果
      for (let rightNode of rightTrees) {
        let root: TreeNode = new TreeNode(i);
        root.left = leftNode;
        root.right = rightNode;
        res.push(root);// 形成新二叉搜索树后返回结果
      }
    }
  }
  return res;
}

// 这道题目是一道难度偏大的递归设计
// 因为题目需要满足二叉搜索树
// 基本的逻辑是利用范围内的一个数将整段数组分组成两段，左半段和右半段
// 然后这个左半段与右半段再分别形成一个新的二叉搜索树
// 再把形成的二叉搜索树拼接在节点的左右两侧，这就完成了一颗满足情况的二叉搜索树
// 但题目中要求可以得到所有的树，所以我们需要把形成的左右两颗二叉搜索树的根节点都存储在一个数组当中
// 在递归的设计上需要首先留意递归的出口，当边界索引不满足合理范围时，记得输出相应结果
// 在主循环中，我们遍历从low到high的元素，用计数器i作为分割左右子树的根节点
// 以 i 为根节点的二叉搜索树种类数 = 左子树种类数 * 右子树种类数
// 完成一颗二叉搜索树的构建后把根节点插入结果数组中即可。